In graph theory, a graph G with vertex set V(G) is said to be k-vertex-connected (or k-connected) if the graph remains connected when you delete fewer than k vertices from the graph. Alternatively, a graph is k-connected if k is the size of the smallest subset of vertices such that the graph becomes disconnected if you delete them.[1]
An equivalent definition for graphs that are not complete is that a graph is k-connected if any two of its vertices can be joined by k independent paths; see Menger's theorem (Diestel 2005, p. 55). However, for complete graphs the two definitions differ: the n-vertex complete graph has unbounded connectivity according to the definition based on deleting vertices, but connectivity n − 1 according to the definition based on independent paths, and some authors use alternative definitions according to which its connectivity is n.[1].
A 1-vertex-connected graph is called connected, while a 2-vertex-connected graph is said to be biconnected.
The vertex-connectivity, or just connectivity, of a graph is the largest k for which the graph is k-vertex-connected.
The 1-skeleton of any k-dimensional convex polytope forms a k-vertex-connected graph (Balinski's theorem, Balinski 1961). As a partial converse, Steinitz's theorem states that any 3-vertex-connected planar graph forms the skeleton of a convex polyhedron.